package com.bear.bearalgo.双向队列;

public class LinkedListDeque {
    /**
     * 双向链表节点
     */
    class ListNode {
        int val;//节点值
        ListNode next;//后继节点引用
        ListNode prev;//前继节点引用

        ListNode(int val) {
            this.val = val;
            prev = next = null;
        }
    }

    private ListNode front, rear;//头节点front，尾节点rear
    private int queSize;//双向队列长度

    public LinkedListDeque() {
        front = rear = null;
    }

    /**
     * 获取双向队列长度
     *
     * @return 双向队列长度
     */
    public int size() {
        return queSize;
    }

    /**
     * 判断双向队列是否为空
     *
     * @return true：为空；false：不为空
     */
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * 入队操作
     */
    private void push(int num, boolean isFront) {
        ListNode node = new ListNode(num);
        //若链表为空，则令front和rear都指向node
        if (isEmpty()) {
            front = rear = node;
        }
        //队首入队操作
        else if (isFront) {
            //将node添加到链表头部
            front.prev = node;//原本的头节点的prev指向node
            node.next = front;//node的next指向原本的头节点  形成一个双向的指向关系
            //⬆️上面两步只是完成了新节点与原来的头节点之间的双向链接

            front = node;//如果没有这一步，原本的front指针仍然指向原本的头节点
        }

        //队尾入队操作
        else {
            //将node添加到链表尾部
            rear.next = node;
            node.prev = rear;
            rear = node;
        }

        //完成入队操作后，队列长度加1
        queSize++;
    }


    /**
     * 队首入队操作
     *
     * @param num 入队元素
     */
    public void pushFirst(int num) {
        push(num, true);
    }
    /**
     * 队尾入队操作
     *
     * @param num 入队元素
     */
    public void pushLast(int num) {
        push(num, false);
    }

    /**
     * 出队操作
     */
    private int pop(boolean isFront) {
        if (isEmpty()) {
            throw new IndexOutOfBoundsException();
        }
        int val;
        //队首出队操作
        if (isFront) {
            val = front.val;//暂存头节点值，这个值后续需要返回给调用者
            //删除头节点
            ListNode fNext = front.next;//这一步拿到链表头的第二个节点，也就是我们出队后的新的队首元素
            if (fNext != null) {
                fNext.prev = null; //第二个节点不再指向原本的头节点
                front.next = null; //队首指针不再引用原来的头节点
            }
            front = fNext;//更新头节点
        }

        //队尾出队操作
        else {
            val = rear.val;//暂存尾节点，最终返回给调用者
            ListNode rPrev = rear.prev;
            if (rPrev != null) {
                rPrev.next = null;
                rear.prev = null;
            }
            rear = rPrev;//更新尾节点
        }
        queSize--;
        return val;
    }


    /**
     * 队首出队
     */
    public int popFirst(){
        return pop(true);
    }
    /**
     * 队尾出队
     */
    public int popLast(){
        return pop(false);
    }


    /**
     * 访问队首元素
     */
    public int peekFirst(){
        if (isEmpty()){
            throw new IndexOutOfBoundsException();
        }
        return front.val;
    }
    /**
     * 访问队尾元素
     */
    public int peekLast(){
        if (isEmpty())
        {throw new IndexOutOfBoundsException();
        }
        return rear.val;
    }


    /**
     * 返回数组用于打印
     */
    public int[] toArray() {
        ListNode node = front;
        int[] res = new int[size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = node.val;
            node = node.next;
        }
        return res;
    }

    public static void main(String[] args) {
        LinkedListDeque deque = new LinkedListDeque();

        // 测试队首入队
        deque.pushFirst(1);
        System.out.println("队首入队 1 后，队列元素: " + arrayToString(deque.toArray()));

        // 测试队尾入队
        deque.pushLast(2);
        System.out.println("队尾入队 2 后，队列元素: " + arrayToString(deque.toArray()));

        // 测试队列长度
        System.out.println("当前队列长度: " + deque.size());

        // 测试访问队首元素
        System.out.println("队首元素: " + deque.peekFirst());

        // 测试访问队尾元素
        System.out.println("队尾元素: " + deque.peekLast());

        // 测试队首出队
        int firstOut = deque.popFirst();
        System.out.println("队首出队元素: " + firstOut + "，出队后队列元素: " + arrayToString(deque.toArray()));

        // 测试队尾出队
        int lastOut = deque.popLast();
        System.out.println("队尾出队元素: " + lastOut + "，出队后队列元素: " + arrayToString(deque.toArray()));

        // 测试队列是否为空
        System.out.println("队列是否为空: " + deque.isEmpty());
    }

    private static String arrayToString(int[] array) {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        for (int i = 0; i < array.length; i++) {
            sb.append(array[i]);
            if (i < array.length - 1) {
                sb.append(", ");
            }
        }
        sb.append("]");
        return sb.toString();
    }
}
